package insertsort

func InsertSort(array []int) []int {
	for i := 1; i < len(array); i++ {
		for j := i; j > 0; j-- {
			if array[j] < array[j-1] {
				array[j], array[j-1] = array[j-1], array[j]
			}
		}
	}
	return array
}

// 插入排序的优化---每次排序的时候，只进行一次插入。
// 我们要考虑的是什么----正常情况下，如果前一个数比我们保存的数大，就让这个数后移一位，如果前一位数比后一位要小的话，直接将保存的数，放到这个位置就可以了。
// 注意的是，当前一个数一直比后一个数小，直到最后一个怎么办？----所以我们要判断一下，如果当前这个数的前一位没有了，就直接赋值就可以了。这个每次循环都要判断，所以放在最外面的一个条件
func InsertSortOptimazation(array []int) []int {
	for i := 1; i < len(array); i++ {
		tmp := array[i]
		for j := i; j >= 0; j-- {
			if j-1 < 0 {
				array[j] = tmp
			} else {
				if tmp < array[j-1] {
					array[j] = array[j-1]
				} else {
					array[j] = tmp
					break
				}

			}
		}
	}
	return array
}
